class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());

        int idx = s.size() - 1, ret = 0;
        for(int i = g.size() - 1; i >= 0; i--)
        {
            // 贪心策略: 大饼干满足胃口大的
            if(idx >= 0 && s[idx] >= g[i])
            {
                ret++;
                idx--;
            }
            if(idx < 0)
                break;
        }
        return ret;


        // 下面是我自己的版本，空间复杂度有点高，是O(N)
        // set<int> set;
        // map<int, int> hash;
        // for(int &x : s)
        // {
        //     set.insert(x);
        //     hash[x]++;
        // }
        // sort(g.begin(), g.end());
        // int ret = 0;
        // for(int &x : g)
        // {
        //     auto it = set.lower_bound(x);
        //     if(it == set.end())
        //         break;
        //     ret++;
        //     if(--hash[*it] == 0)
        //         set.erase(*it);
        // }
        // return ret;
    }
};